#include <stdio.h>
#include <stdlib.h>
#include "arista.h"
#include "colap.h"
#include "uf.h"
#include "cra.h"
#include "cintwar.h"
#include "stack.h"

void
print_colap(Colap cp);


int main (void)
{
	Colap cp;
	union_find ccv;
	cintrar cr;
	cintwar cw;
	Stack s1,s2;
	Arista e;
	tufset cv1,cv2;

	int numV, numA;

	cp = NULL;
	ccv = NULL;
	cr = NULL;
	cw = NULL;
	s1 = NULL;
	s2 = NULL;
	e = NULL;

/* CONSTRUCCIÓN E INICIALIZACIÓN DE LOS TAD'S */

	cr = cra_create(); /*creo la cinta de lectura y la arranco */
	cra_arr(cr);

	numV = cra_cantvert(cr);
	numA = cra_cantaris(cr);

	cp = colap_create(numA);
	s1 = stack_empty(numA);
	s2 = stack_empty(numA);
	ccv = uf_create(numV);

/* -------------------------------------- */

	while (!(cra_fin(cr)))	/* se leen todas las aristas, se las "ordena" y se las manda al uf */
	{
		e = cra_elec(cr);
		colap_encolar(cp,e);
		uf_add_singulete(ccv,arista_fst(e));
		uf_add_singulete(ccv,arista_snd(e));
		cra_av(cr);
		e = arista_destroy(e);

	}

	while (!(uf_oneset(ccv)) && !(colap_vacia(cp)))
	{
		e = colap_primero(cp);
		colap_pop(cp);
		cv1 = uf_find(ccv, arista_fst(e));
		cv2 = uf_find(ccv, arista_snd(e));
		if (cv1 != cv2)
		{
			uf_union(ccv,cv1,cv2);
			stack_push(s1,e);	/*en s1 se guardan las aristas del MST y en s2 las que no */
		}
		else
		{
			stack_push(s2,e);
		}
		e = arista_destroy(e); 
	}

	cr = cra_destroy(cr); /* termine de leer */
	cw = cwa_create(); /*empiezo a escribir */
	cwa_arr(cw);

	while (!(isEmpty_stack(s1)))
	{
		e = stack_top(s1);
		stack_pop(s1);
		cwa_insarbol(cw,e);
		e = arista_destroy(e);
	}

	while (!(isEmpty_stack(s2)))
	{
		e = stack_top(s2);
		stack_pop(s2);
		cwa_ainsrest(cw,e);
		e = arista_destroy(e);
	}

	while (!(colap_vacia(cp)))
	{
		e = colap_saca(cp);
		cwa_ainsrest(cw,e);
		e = arista_destroy(e);
	}

/* DESTRUCCIÓN DE LOS TAD'S */

	cw = cwa_destroy(cw);
	s1 = stack_destroy(s1);
	s2 = stack_destroy(s2);
	ccv = uf_destroy(ccv);
	cp = colap_destroy(cp);

return 0;
}
